abstract class Block {
  private ArrayList<PVector> vertices;
  private ArrayList<PVector> hull;
  PVector centroid;
  float area;
  private Rectangle rectangle;
  private float tolerance = 400; // etäisyyden neliö, käytetään palikoiden samankaltaisuuden tarkistuksessa
  private float proximity = 40000; // etäisyyden neliö, käytetään pisteen/palikoiden läheisyyden tarkistuksessa
  private float ratio = 0.2; // sallittu ero pienimmän pistejoukon ympäröivän suorakaiteen leveyden ja korkeuden suhteessa, käytetään palikoiden samankaltaisuuden tarkistuksessa
  
  PVector velocity;
  private LinkedList<PVector> velocities;
  private int velocityBufferSize = 5;
  private float deceleration = 0.99;

  Block() {
    this.vertices = new ArrayList<PVector>();
    this.hull = null;
    this.centroid = null;
    this.rectangle = null;
    
    this.velocity = null;
    this.velocities = new LinkedList<PVector>();
  }

  // palauttaa palikan pisteiden lukumäärän
  int size() {
    return this.vertices.size();
  }
  
  void addVelocityBuffer(float vx, float vy) {
    this.velocities.add(new PVector(vx, vy));
    if (this.velocities.size() >= 6) {
      this.velocities.remove();
    }
  }
  
  void setVelocity() {
    if (this.velocities.size() == 0) return;
    float magnitude = 0;
    PVector unit = this.velocities.getLast().get();
    unit.normalize();
    Iterator iter = this.velocities.iterator();
    while (iter.hasNext()) {
      magnitude += ((PVector)iter.next()).dot(unit);
    }
    unit.mult(magnitude / this.velocities.size());
    this.velocity = unit;
  }
  
  void resetVelocity() {
    this.velocity = null;
    this.velocities.clear();
  }
  
  void go() {
    if (this.velocity == null) return;
    this.translate(this.velocity.x, this.velocity.y);
    this.velocity.mult(this.deceleration);
    if (this.velocity.dot(this.velocity) < 1) {
      this.resetVelocity();
    }
  }
  
  void updateCentroid() {
    if (this.size() == 0) {
      this.centroid = null;
    }
    else if (this.size() == 1) {
      this.centroid = this.vertices.get(0).get();
    }
    else if (this.size() == 2) {
      this.centroid = PVector.mult(PVector.add(this.vertices.get(0), this.vertices.get(1)), 0.5);
    }
    else {
      this.centroid = this.hullCentroid();
    }
  }

  // lisää palikkaan pisteen (x, y)
  void add(float x, float y) {
    this.add(x, y, -1);
  }

  // lisää palikkaan pisteen (x, y) kursorista (id)
  void add(float x, float y, long id) {
    this.vertices.add(new PVector(x, y, id));
    if (this.size() > 3 && !this.insideHull(x, y)) { // insideHull():ssa float epätarkkuutta
      this.convexHull();
      this.boundingRect();
    }
    else if (this.size() == 3) {
      this.convexHull();
      this.boundingRect();
    }
    this.updateCentroid();
  }

  // poistaa palikasta pisteen kursorista (id)
  boolean remove(long id) {
    for (int i = 0; i < this.size(); ++i) {
      PVector v = this.vertices.get(i);
      if (v.z == id) {
        this.vertices.remove(i);
        if (this.size() >= 3 && this.hull.contains(v)) {
          this.convexHull();
          this.boundingRect();
        }
        else if (this.size() == 2) {
          this.hull = null;
          this.rectangle = null;
        }
        this.updateCentroid();
        return true;
      }
    }
    return false;
  }

  // tarkistaa löytyykö kursori (id) tästä palikasta
  boolean contains(long id) {
    for (PVector v : this.vertices) {
      if (v.z == id) {
        return true;
      }
    }
    return false;
  }

  // http://learn2program.wordpress.com/2007/06/16/the-point-in-the-polygon-or-not/
  boolean insideHull(float x, float y) {
    if (this.hull == null) return false;
    boolean in = false;
    for (int i = 0, j = this.hull.size() - 1; i < this.hull.size(); j = i++) {
      PVector v1 = this.hull.get(i);
      PVector v2 = this.hull.get(j);
      if ((((v1.y <= y) && (y < v2.y)) || ((v2.y <= y) && (y < v1.y))) && (x < (v2.x - v1.x) * (y - v1.y) / (v2.y - v1.y) + v1.x)) {
        in = !in;
      }
    }
    return in;
  }

  float hullArea() {
    if (this.hull == null) return -1;
    float area = 0;
    for (int i = 0, j = this.hull.size() - 1; i < this.hull.size(); j = i++) {
      PVector v1 = this.hull.get(i);
      PVector v2 = this.hull.get(j);
      area += v2.x * v1.y - v1.x * v2.y;
    }
    return 0.5 * area;
  }

  PVector hullCentroid() {
    if (this.hull == null) return null;
    PVector v = new PVector();
    for (int i = 0, j = this.hull.size() - 1; i < this.hull.size(); j = i++) {
      PVector v1 = this.hull.get(i);
      PVector v2 = this.hull.get(j);
      v.x += (v1.x + v2.x) * (v2.x * v1.y - v1.x * v2.y);
      v.y += (v1.y + v2.y) * (v2.x * v1.y - v1.x * v2.y);
    }
    this.area = this.hullArea();
    v.div(6 * this.area);
    return v;
  }

  // siirtää kursorin (id) paikkaan (x, y)
  boolean update(float x, float y, long id) {
    for (PVector v : this.vertices) {
      if (v.z == id) {
        //boolean before = this.insideHull(v.x, v.y);
        //boolean after = this.insideHull(x, y);
        v.set(x, y, id);
        if (this.hull != null/* && (this.hull.contains(v) || before != after)*/) {
          this.convexHull();
          this.boundingRect();
        }
        this.updateCentroid();
        return true;
      }
    }
    return false;
  }
  
  PVector getVertex(int id) {
    for (PVector v : this.vertices) {
      if (v.z == id) {
        return v;
      }
    }
    return null;
  }

  // siirtää palikkaa matkan (x, y) verran
  void translate(float x, float y) {
    PVector t = new PVector(x, y);
    for (PVector v : this.vertices) {
      v.add(t);
    }
    if (this.size() >= 3) {
      for (PVector h : this.hull) {
        h.add(t);
      }
      this.rectangle.translate(t);
    }
    this.centroid.add(t);
  }

  // http://www.openprocessing.org/visuals/?visualID=1874
  void convexHull() {
    this.hull = new ArrayList<PVector>();
    class VertexComparator implements Comparator<PVector> {
      public int compare(PVector v1, PVector v2) {
        if (v1.y > v2.y || (v1.y == v2.y && v1.x > v2.x)) return 1;
        else return -1;
      }
    }
    Collections.sort(this.vertices, new VertexComparator());
    for (PVector v : this.vertices) {
      while (this.hull.size () >= 2 && this.canSee(this.hull.get(this.hull.size() - 2), this.hull.get(this.hull.size() - 1), v) <= 0) {
        this.hull.remove(this.hull.size() - 1);
      }
      this.hull.add(new PVector(v.x, v.y));
    }
    for (int i = this.vertices.size() - 2, t = this.hull.size() + 1; i >= 0; --i) {
      while (this.hull.size () >= t && this.canSee(this.hull.get(this.hull.size() - 2), this.hull.get(this.hull.size() - 1), this.vertices.get(i)) <= 0) {
        this.hull.remove(hull.size() - 1);
      }
      this.hull.add(new PVector(this.vertices.get(i).x, this.vertices.get(i).y));
    }
    this.hull.remove(hull.size() - 1);
  }

  private float canSee(PVector a, PVector b, PVector c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  }

  private float minAngle(ArrayList<PVector> hullCopy, Rectangle minRect) {
    PVector v = hullCopy.get(0);
    PVector[] outerVertices = new PVector[] {
      v, v, v, v
    };
    for (int i = 1; i < hullCopy.size(); ++i) {
      v = hullCopy.get(i);
      if (v.x <= outerVertices[0].x) {
        outerVertices[0] = v;
      }
      if (v.y <= outerVertices[1].y) {
        outerVertices[1] = v;
      }
      if (v.x >= outerVertices[2].x) {
        outerVertices[2] = v;
      }
      if (v.y >= outerVertices[3].y) {
        outerVertices[3] = v;
      }
    }
    minRect.set(outerVertices[0].x, outerVertices[2].x, outerVertices[1].y, outerVertices[3].y);
    float minAngle = 2 * PI;
    PVector[] calipers =  new PVector[] {
      new PVector(0, -1), new PVector(1, 0), new PVector(0, 1), new PVector(-1, 0)
    };
    for (int i = 0; i < outerVertices.length; ++i) { // korjaa tämä iterointi + muut vastaavat
      int index = hullCopy.indexOf(outerVertices[i]);
      PVector edge = PVector.sub(hullCopy.get(++index == hullCopy.size() ? 0 : index), outerVertices[i]);
      float angle = PVector.angleBetween(calipers[i], edge);
      if (angle > 0.001 && angle < minAngle) {
        minAngle = angle;
      }
    }
    return minAngle;
  }

  void boundingRect() {
    if (hull == null) return;
    ArrayList<PVector> hullCopy = this.copyArrayList(this.hull);
    float limit = 0.5 * PI;
    Rectangle minBoundingRect = null;	
    float minArea = -1;
    float cumulativeAngle = 0;
    float cumulativeMinAngle = 0;
    while (cumulativeAngle <= limit) {
      Rectangle minRect = new Rectangle();
      float minAngle = minAngle(hullCopy, minRect);
      float rectArea = minRect.area();
      if (rectArea < minArea || minArea < 0) {
        minArea = rectArea;
        cumulativeMinAngle = cumulativeAngle;
        minBoundingRect = minRect;
      }
      cumulativeAngle += minAngle;
      for (PVector v : hullCopy) {
        v.rotate(-minAngle);
      }
    }
    minBoundingRect.rotate(cumulativeMinAngle);
    this.rectangle = minBoundingRect;
  }

  private ArrayList<PVector> copyArrayList(ArrayList<PVector> al) {
    if (al == null || al.size() == 0) return null;
    ArrayList<PVector> alCopy = new ArrayList<PVector>(al.size());
    for (PVector v : al) {
      alCopy.add(v.get());
    }
    return alCopy;
  }

  ArrayList<PVector> normalize() {
    ArrayList<PVector> verticesCopy = this.copyArrayList(this.vertices);
    Rectangle rectCopy = new Rectangle(this.rectangle);
    for (PVector v : verticesCopy) {
      v.sub(rectCopy.c);
    }
    rectCopy.translate(PVector.mult(rectCopy.c, -1));
    PVector caliper = new PVector(1, 0);
    PVector edge = PVector.sub(rectCopy.vertices[1], rectCopy.vertices[0]);
    float angle = PVector.angleBetween(caliper, edge);
    for (PVector v : verticesCopy) {
      v.rotate(-angle);
    }
    rectCopy.rotate(-angle);
    float dx = rectCopy.vertices[1].dist(rectCopy.vertices[0]);
    float dy = rectCopy.vertices[2].dist(rectCopy.vertices[1]);
    if (dx < dy) {
      for (PVector v : verticesCopy) {
        v.rotate(0.5 * PI);
      }
      float temp = dx;
      dx = dy;
      dy = temp;
    }
    dx *= 0.5;
    dy *= 0.5;
    for (PVector v : verticesCopy) {
      v.div(new PVector(dx, dy, 1));
      v.mult(new PVector(200, 100));
    }
    return verticesCopy;
  }
  
  private PVector nearVertex(PVector v, ArrayList<PVector> b) {
    PVector d = PVector.sub(v, b.get(0));
    PVector minDV = b.get(0);
    float minD = d.dot(d);
    for (int i = 1; i < b.size(); ++i) {
      d = PVector.sub(v, b.get(i));
      float currD = d.dot(d);
      if (currD < minD) {
        minD = currD;
        minDV = b.get(i);
      }
    }
    return minD <= this.tolerance ? minDV : null;
  }

  boolean similar(Block other) {
    if (this.size() != other.size() || this.size() < 3) return false;
    float ratio1 = this.rectangle.w > this.rectangle.h ? this.rectangle.w / this.rectangle.h : this.rectangle.h / this.rectangle.w;
    float ratio2 = other.rectangle.w > other.rectangle.h ? other.rectangle.w / other.rectangle.h : other.rectangle.h / other.rectangle.w;
    if (abs(ratio2 - ratio1) > ratio) return false;
    boolean isSimilar = true;
    ArrayList<PVector> b1 = this.normalize();
    ArrayList<PVector> b2 = other.normalize();
    ArrayList<PVector> b1Copy = this.copyArrayList(b1);
    ArrayList<PVector> b2Copy = this.copyArrayList(b2);
    Iterator iter = b1.iterator();
    while (iter.hasNext()) {
      PVector v1 = (PVector)iter.next();
      PVector v2 = this.nearVertex(v1, b2);
      if (v2 != null) {
        iter.remove();
        b2.remove(v2);
        continue;
      }
      isSimilar = false;
      break;
    }
    if (isSimilar) return true;
    for (PVector v : b1Copy) {
      v.rotate(PI);
    }
    iter = b1Copy.iterator();
    while (iter.hasNext()) {
      PVector v1 = (PVector)iter.next();
      PVector v2 = this.nearVertex(v1, b2Copy);
      if (v2 != null) {
        iter.remove();
        b2Copy.remove(v2);
        continue;
      }
      return false;
    }
    return true;
  }

  float dist(float x, float y) {
    return sqrt(this.dist2(x, y));
  }

  float dist2(float x, float y) {
    if (this.centroid == null) {
      return Float.POSITIVE_INFINITY;
    }
    float dx = x - this.centroid.x;
    float dy = y - this.centroid.y;
    return dx * dx + dy * dy;
  }
  
  float dist(Block other) {
    return sqrt(this.dist2(other));
  }
  
  float dist2(Block other) {
    if (this.centroid == null) {
      return Float.POSITIVE_INFINITY;
    }
    return other.dist2(this.centroid.x, this.centroid.y);
  }

  boolean near(float x, float y) {
    return this.dist2(x, y) <= this.proximity;
  }
  
  boolean near(Block other) {
    return this.dist2(other) <= this.proximity;
  }

  // laajentaa tätä palikkaa, mutta ei tuhoa toista palikkaa!
  Block merge(Block other) {
    this.vertices.addAll(other.vertices);
    if (this.size() >= 3) {
      this.convexHull();
      this.boundingRect();
    }
    this.updateCentroid();
    return this;
  }

  abstract void draw();

  void drawConvexHull() {
    if (this.hull == null) return;
    pushStyle();
    stroke(255, 0, 0);
    beginShape();
    for (int i = 0; i < this.hull.size(); ++i) {
      vertex(this.hull.get(i).x, this.hull.get(i).y);
      pushStyle();
      fill(0);
      text(i, this.hull.get(i).x + 15, this.hull.get(i).y + 15);
      popStyle();
    }
    endShape(CLOSE);
    line(this.centroid.x - 10, this.centroid.y - 10, this.centroid.x + 10, this.centroid.y + 10);
    line(this.centroid.x - 10, this.centroid.y + 10, this.centroid.x + 10, this.centroid.y - 10);
    popStyle();
  }

  void drawBoundingRect() {
    if (this.rectangle == null) return;
    this.rectangle.draw();
  }
}
